| partial class UGRAPH_INCL{NTP} < $UGRAPH{NTP} |
|---|
| **** | Partial class used to define useful routines in undirected graphs that are based on a core set of (undefined) routines The core routines must be defined by a particular implementation upon inclusion |
| $UGRAPH{_} | $RO_UGRAPH{_} | $GRAPH{_,_} | $STR | $ELT{_} | $ELT | COMPARE{_} |
| UGRAPH{_} |
| stub add_node(n: NTP); |
|---|
| stub add_node(n: NTP):NTP; |
|---|
| stub add_node: NTP; |
|---|
| adjacent(n: NTP): SET{NTP} |
|---|
| are_connected(n1,n2: NTP): BOOL |
|---|
| **** | Return true if there exists a path from n1 to n2 |
| stub connect(n1,n2: NTP); |
|---|
| connect(e: UEDGE{NTP}) |
|---|
| stub copy: SAME; |
|---|
| stub create: SAME; |
|---|
| **** | Some of the routines need to create a "fresh" graph. |
| stub delete_node(n: NTP); |
|---|
| delete_reflexive_edges |
|---|
| **** | Delete all reflexive edges from the graph |
| dfs_apply(n: NTP,wk:ROUT{NTP}) |
|---|
| **** | Apply the pre visit work "wk" to nodes in df order. Non recursive |
| dfs_apply(n: NTP,prewk:ROUT{NTP},postwk:ROUT{UEDGE{NTP}}) |
|---|
| **** | Perform pre work before visiting a node and perform postwk on the way back up each edge Recursive version of dfs (much simpler to code) Here postwork is applied to *all* edges, including back edges |
| difference(g:$UGRAPH{NTP}): $UGRAPH{NTP} |
|---|
| stub disconnect(n1,n2: NTP); |
|---|
| disconnect(e: UEDGE{NTP}) |
|---|
| edges: SET{UEDGE{NTP}} |
|---|
| equals(g: $RO_UGRAPH{NTP}): BOOL |
|---|
| **** | Check that nodes and edges are the same Very inefficient n^2 version - sort for nlogn version |
| has(n: NTP): BOOL |
|---|
| has_edge(first,second: NTP): BOOL |
|---|
| has_edge(e: UEDGE{NTP}):BOOL |
|---|
| has_node(n: NTP): BOOL |
|---|
| has_same_nodes(g: $RO_UGRAPH{NTP}): BOOL |
|---|
| induced_subgraph(v: $SET{NTP}): $UGRAPH{NTP} |
|---|
| **** | Generate a subgraph which is induced by the edges "v". |
| is_empty: BOOL |
|---|
| n_adjacent(n: NTP): INT |
|---|
| n_edges: INT |
|---|
| n_nodes: INT |
|---|
| n_reachable_from(n: NTP): INT |
|---|
| node_depths(n: NTP,map:$MAP{NTP,INT}) |
|---|
| **** | map should be inout, but this will work for now Do a bfs and return depths of each node |
| nodes: SET{NTP} |
|---|
| reachable_from(n: NTP): SET{NTP} |
|---|
| **** | Returns the set of nodes reachable from "n" |
| roots: SET{NTP} |
|---|
| **** | Returns a list of "representative" nodes from which the whole graph is reachable. With inout args, also return a mapping from nodes to the appropriate representative nodes (i.e. seen) |
| size: INT |
|---|
| str(f: ROUT{NTP}:STR): STR |
|---|
| **** | Print out the graph using the bound routine "f" for the nodes |
| str: STR |
|---|
| to_difference(g: $UGRAPH{NTP}) |
|---|
| to_transitive_closure |
|---|
| **** | Convert the graph to it's transitive closure For a non-destructive version, first make a copy |
| to_union(g: $UGRAPH{NTP}) |
|---|
| union(g: $UGRAPH{NTP}): $UGRAPH{NTP} |
|---|
| stub adjacent!(once n: NTP): NTP; |
|---|
| bfs!(once n: NTP): NTP |
|---|
| **** | Return all nodes reachable from "n" in bf order |
| dfs!(once n: NTP): NTP |
|---|
| **** | Return all nodes reachable from "n" in df order |
| edge!: UEDGE{NTP} |
|---|
| elt!: NTP |
|---|
| filter_edge!(once |
|---|
| **** | Return a set of edge tuples that are true for test "et" |
| filter_node!(once |
|---|
| **** | Return the set of all nodes in g that satisfy the node test "nt" |
| stub node!: NTP; |
|---|
| reachable_from!(once n: NTP): NTP |
|---|
| **** | Returns successive nodes reachable from "n" using dfs |
| dfs_rec(seen:FSET{NTP},n:NTP,bef:ROUT{NTP},aft:ROUT{UEDGE{NTP}}) |
|---|
| **** | Recursive depth first search, when both pre and postwork must be done. Seen holds the list of nodes already seen |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| node_str(n: NTP): STR |
|---|